package link_list;

import java.util.*;

public class ReverseBetween {
    public static void main(String[] args) {
//        ListNode one = null;
        ListNode one = new ListNode(1);
        ListNode two = new ListNode(2);
        ListNode three = new ListNode(3);
        ListNode four = new ListNode(4);
        ListNode five = new ListNode(5);
        one.next = two;
        two.next = three;
        three.next = four;
        four.next = five;
        ListNode listNode = newReverseBetween(one, 2, 3);
        while (!Objects.isNull(listNode)) {
            System.out.println(listNode.val);
            listNode = listNode.next;
        }
    }

    static class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        // write code here
        int left = 0;
        int right = lists.size() - 1;
        ListNode chai = chai(lists, left, right);
        return chai;
    }
    public ListNode chai(List<ListNode> lists,int left,int right){
        if(left == right) return lists.get(left);
        int mid = (left + right) / 2;
        ListNode l = chai(lists,left,mid);
        ListNode r = chai(lists,mid + 1,right);
        return mergerO(l,r);
    }
    public ListNode mergerO(ListNode oHead, ListNode tHead) {
        if (Objects.isNull(oHead) || Objects.isNull(tHead)) return Objects.isNull(oHead) ? tHead : oHead;
        if(oHead.val < tHead.val){
            oHead.next = mergerO(oHead.next,tHead);
            return oHead;
        }else{
            tHead.next = mergerO(oHead,tHead.next);
            return tHead;
        }
    }

    public ListNode merge(ListNode pHead1, ListNode pHead2) {
        ListNode three = new ListNode(-999);
        ListNode threeCp = three;
        //7 8 9
        //2 4 6
        //1 2 3 4 5
        while (!Objects.isNull(pHead1) && !Objects.isNull(pHead2)) {
            if (pHead1.val < pHead1.val) {
                three.next = pHead1;
                pHead1 = pHead1.next;
            } else {
                three.next = pHead2;
                pHead2 = pHead2.next;
            }
            three = three.next;
        }
        if (Objects.isNull(pHead1)) {
            three.next = pHead2;
        } else {
            three.next = pHead1;
        }
        return threeCp.next;
    }

    public static ListNode reverseKGroup(ListNode head, int k) {
        if (Objects.isNull(head)) {
            return null;
        }
        // write code here
        ListNode point = head;
        ArrayList<ListNode> nodes = new ArrayList<>();
        while (!Objects.isNull(point)) {
            nodes.add(point);
            point = point.next;
        }
        int curK = k - 1;
        int curP = 0;
        while (curK < nodes.size()) {
            int right = curK;
            int left = curP;
            ListNode swap = null;
            while (right > left) {
                swap = nodes.get(right);
                nodes.set(right, nodes.get(left));
                nodes.set(left, swap);
                right--;
                left++;
            }
            curK += k;
            curP += k;
        }
        ListNode newHead = nodes.get(0);
        for (int i = 1; i < nodes.size(); i++) {
            newHead.next = nodes.get(i);
            newHead = newHead.next;
        }
        nodes.get(nodes.size() - 1).next = null;
        return nodes.get(0);
    }

    public static ListNode reverseBetween(ListNode head, int m, int n) {
        int size = 0;
        ListNode headCp = head;
        while (!Objects.isNull(headCp)) {
            headCp = headCp.next;
            size++;
        }
        ListNode[] resultArray = new ListNode[size];
        int target = 1;
        int ntarget = n;
        while (!Objects.isNull(head)) {
            if (target >= m && target <= n) {
                resultArray[ntarget - 1] = head;
                ntarget--;
            } else {
                resultArray[target - 1] = head;
            }
            target++;
            head = head.next;
        }
        ListNode resultHead = resultArray[0];
        for (int i = 1; i < resultArray.length; i++) {
            resultHead.next = resultArray[i];
            resultHead = resultHead.next;
        }
        resultArray[size - 1].next = null;
        return resultArray[0];
    }

    public static ListNode newReverseBetween(ListNode head, int m, int n) {
        int mPre = 0;
        int nLast = 0;
        ListNode first = head;
        if (m == 1) {
            first = null;
        }
        while (mPre < m - 2) {
            first = first.next;
            mPre++;
        }
        ListNode second = head;
        while (nLast < n) {
            second = second.next;
            nLast++;
        }
        ListNode between = null;
        if (first == null) {
            between = head;
        } else {
            between = first.next;
        }
        int count = n - m;
        Stack<ListNode> nodes = new Stack<>();
        while (count >= 0) {
            nodes.push(between);
            between = between.next;
            count--;
        }
        ListNode betweenTail = nodes.pop();
        ListNode betweenHead = betweenTail;
        while (!nodes.isEmpty()) {
            ListNode pop = nodes.pop();
            betweenTail.next = pop;
            betweenTail = pop;
        }
        betweenTail.next = second;
        if (first == null) {
            return betweenHead;
        }
        first.next = betweenHead;
        return head;
    }
}